package sort;

public class HeapSort2 {

	public static void main(String[] args) {
		int[] array = { 5, 56, 8984, 65, -1, 9, -9, 56,57,59,60, 131, 561, 29, -94, 15, 3,
				4, 5, 1, 513, 235 };
		heapSort(array);
		
		for (int j : array) {
			System.out.print(j + " ");
		}
		System.out.println();
	}

	public static void heapSort(int[] array) {
		int length = array.length;
		for (int i = length / 2 - 1; i >= 0; i--) {
			adjustHeap(array, i, length);
		}

		// 大根堆建立好之后，进行上筛过程
		for (int i = length - 1; i > 0; i--) {
			MaoPaoSort.swap(array, i, 0);
			adjustHeap(array, 0, i);
		}

		for (int j : array) {
			System.out.print(j + " ");
		}
		System.out.println();
	}

	public static void adjustHeap(int[] array, int i, int length) {
		int temp = array[i];
		// 完全二叉树中，若以1开头算根节点，i结点的左右子节点分别为 2 * i，2 * i + 1
		int childPos = (i + 1) * 2 - 1; // 初始为左结点
		if (i <= length / 2) {
			// 可能i结点的左结点是最后一个结点
			if (childPos < length - 1 && array[childPos + 1] > array[childPos]) {
				childPos += 1;
			}
			// 如果左右结点中的最大值比根节点大，则交换
			if (childPos < length && array[childPos] > temp) {
				MaoPaoSort.swap(array, childPos, i);
				adjustHeap(array, childPos, length); // 重新调整子结点
			}
		}
	}
}
